package a07_二叉树;

import java.util.Arrays;

/**
 * <p>
 * a32_将有序数组转换为二叉搜索树
 * </p>
 *
 * @author flyduck
 * @since 2024/12/26
 */
public class a32_将有序数组转换为二叉搜索树 {

    public static void main(String[] args) {
        a32_将有序数组转换为二叉搜索树 test = new a32_将有序数组转换为二叉搜索树();
        int[] array = new int[]{-10,-3,0,5,9};
        TreeNode treeNode = test.sortedArrayToBST(array);
        System.out.println(treeNode);
    }

    //如果是二叉搜索树，直接成单链表就成功了，此题主要是构造平衡二叉搜索树
    //选中间位置作为根节点，才能保证平衡
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }

    public TreeNode traversal(int[] nums,int leftIdx,int rightIdx){
        if(leftIdx > rightIdx){
            return null;
        }
        int middleIdx = leftIdx + (rightIdx - leftIdx)/2;
        TreeNode rootNode = new TreeNode(nums[middleIdx]);
        rootNode.left = traversal(nums,leftIdx,middleIdx - 1);
        rootNode.right = traversal(nums,middleIdx + 1,rightIdx);
        return rootNode;
    }



}
